package com.xxwy.lintcodes;

import com.xxwy.Twopoints;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author xxwy
 * recoverRotatedSortedArray
 * 给定一个旋转排序数组，在原地恢复其排序。
 * 样例
 * 样例1:
 * [4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]
 * 样例2:
 * [6,8,9,1,2] -> [1,2,6,8,9]
 * <p>
 * 解题：
 * 翻转 4 ，5 == 5 ，4
 * 翻转 1，2，3  == 3,2,1
 * 翻转 5,4,3,2,1 == 1,2,3,4,5
 */
@Twopoints
public class Num39 {

    public void recoverRotatedSortedArray(List<Integer> nums) {
        // write your code here
        for (int i = 0; i < nums.size() - 1; i++) {
            //7,9,2,4
            if (nums.get(i) > nums.get(i + 1)) {
                recover(nums, 0, i);
                recover(nums, i + 1, nums.size() - 1);
                recover(nums, 0, nums.size() - 1);
                return;
            }
        }

    }

    private void recover(List<Integer> nums, int l, int r) {
        while (l  < r) {
            Integer lNum = nums.get(l);
            nums.set(l, nums.get(r));
            nums.set(r, lNum);
            l++;
            r--;
        }
    }

    public static void main(String[] args) {
        List<Integer> integers = Arrays.asList(4, 5, 1, 2, 3);
        new Num39().recoverRotatedSortedArray(integers);
    }

}
